package com.buddy.summary.code.algorithm;

import java.util.Arrays;

public class Algorithm_11 {
    //1.在一个无序数组中右99个不重复的正整数，1~100,然后找到缺失的
    private static int findMiss(int[] arr) {
        int sum = 0;
        for (int i = 1; i <= 100; i++) {
            sum += i;
        }
        for (int i = 0; i < arr.length; i++) {
            sum = sum - arr[i];
        }
        return sum;
    }

    //2.找到唯一的出现奇数次的数字
    private static int getOddNum(int[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            result ^= arr[i];
        }
        return result;
    }


    //3.找到两个出现奇数次的数字
    private static int[] getOddNum2(int[] arr) {
        int result[] = new int[2];
        //第一次进行整体异或
        int xorResult = 0;
        for (int i = 0; i < arr.length; i++) {
            xorResult ^= arr[i];
        }
        if (xorResult == 0) {
            return null;
        }
        //确定两个整数的不同位，依次来分组
        int separator = 1;
        while (0 == (xorResult & separator)) {
            separator <<= 1;
        }
        //第二次进行分组异或运算
        for (int i=0;i<arr.length;i++){
            if (0==(arr[i]&separator)){
                result[0] ^= arr[i];
            }else{
                result[1] ^= arr[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = new int[99];
        for (int i = 0; i < 99; i++) {
            arr[i] = i + 1;
        }
        System.out.println(findMiss(arr));
        System.out.println(getOddNum(new int[]{3, 3, 4, 5, 4, 3, 3, 2, 2, 1, 1}));
        System.out.println(Arrays.toString(getOddNum2(new int[]{4,1,2,2,5,1,4,3})));
    }
}
